package HighMethod03;

import java.util.Stack;

/**
 * 二叉排序树
 */
class BSTree {
    class BstNode {
        int key;        //数据
        BstNode leftchild;
        BstNode parent;         //双亲节点
        BstNode rightchild;



        public BstNode() {
            key = 0;
            leftchild = parent = leftchild = null;
        }

        public BstNode(int x) {
            key = x;
            leftchild = parent = leftchild = null;
        }

        public BstNode(int x, BstNode left, BstNode pa, BstNode right) {
            key = x;
            leftchild = left;
            parent = pa;
            rightchild = right;
        }

    }

    BstNode root;       //根节点
    BstNode cur;        //当前节点


    public BSTree() {
        root = null;
        cur = null;
    }

    private BstNode Search(BstNode ptr, int kx) {
        if (ptr == null || ptr.key == kx) {
            return ptr;
        } else if (kx < ptr.key) {
            return Search(ptr.leftchild, kx);
        } else {
            return Search(ptr.rightchild, kx);
        }
    }

    //a、递归，查找kx是否存在
    public boolean SearchValue(int kx) {
        boolean res = false;
        cur = Search(root, kx);
        if (cur != null) {
            res = true;
        }
        return res;
    }

    //b、非递归，查找kx是否存在
    public boolean FindValue(int kx) {
        cur = root;
        boolean res = false;
        while (cur != null && cur.key != kx) {
            cur = kx < cur.key ? cur.leftchild : cur.rightchild;        //精辟
        }
        // cur ！= null 说明（&& cur.key == kx）成立
        if (cur != null) {
            res = true;
        }
        return res;
    }

    //向二叉排序树中，插入一个kx
    public boolean Insert(int kx) {
        boolean res = true;
        if (root == null) {
            //根节点为空，就创建为根节点，返回true
            root = new BstNode(kx);
            return res;
        }
        //如果根节点不为空，cur作为遍历节点，即标记
        cur = root;
        //记录前一个节点
        BstNode pa = null;
        while (cur != null && cur.key != kx) {
            pa = cur;
            cur = kx < cur.key ? cur.leftchild : cur.rightchild;
        }
        //如果找到了(&& cur.key == kx)，就不能插入，返回false
        if (cur != null) {
            res = false;
        } else {
            //没有找到，就创建一个新节点
            cur = new BstNode(kx);
            cur.parent = pa;
            if (cur.key < pa.key) {
                //如果比父节点小，就作为左儿子
                pa.leftchild = cur;
            } else {
                //如果比父节点大，就作为右儿子
                pa.rightchild = cur;
            }
        }
        return res;
    }

    //非递归，先序遍历
    public void NicePreOrder() {
        if (root == null) return;
        Stack<BstNode> st = new Stack<>();
        st.push(root);
        while (!st.empty()) {
            BstNode ptr = st.peek();
            st.pop();
            System.out.print(ptr.key + " ");
            if (ptr.rightchild != null) {
                st.push(ptr.rightchild);
            }
            if (ptr.leftchild != null) {
                st.push(ptr.leftchild);
            }
        }
        System.out.println();
    }

    //非递归的中序遍历
    public void NiceInOrder() {
        if (root == null) return;
        Stack<BstNode> st = new Stack<>();
        cur = root;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.leftchild;
            }
            cur = st.pop();
            System.out.print(cur.key + " ");
            cur = cur.rightchild;
        }
        System.out.println();
    }

    //按照中序遍历顺序创建双链表，注意：该函数会改变二叉排序树的结构谨慎操作！！！
    public void InOrderList() {
        if (root == null) return;
        Stack<BstNode> st = new Stack<>();
        cur = root;
        BstNode pr = null;
        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.leftchild;
            }
            cur = st.pop();
            if (pr == null) {
                root = cur;             //这时的root相当于双链表的头结点
                pr = cur;
            } else {
                pr.rightchild = cur;        //用pr的rightchild充当next指针
                cur.leftchild = pr;         //这里的leftchild充当pre指针
                pr = cur;                   //更新pr
            }
            cur = cur.rightchild;       //中序遍历的
        }
        System.out.println();
    }

    //不使用栈不使用队列，中序打印二叉排序树
    public void PrintList() {
        BstNode p = root;
        while (p != null) {
            System.out.print(p.key + " ");
            p = p.rightchild; //next
        }
        System.out.println();
    }

    //判断是否是二叉排序树
    public boolean Is_BSTree() {
        boolean res = true;
        if (root == null) return res;
        Stack<BstNode> st = new Stack<>();
        cur = root;

        BstNode pre = null;     //记录前一个节点，用于比较顺序是否符合二叉排序树的规则
        while (cur != null || !st.isEmpty()) {
            while (cur != null) {
                st.push(cur);
                cur = cur.leftchild;
            }
            cur = st.pop();
            //让标记节点pre与当前节点即根节点比较
            if (pre != null && pre.key >= cur.key) {
                res = false;
                break;
            }
            pre = cur;
            cur = cur.rightchild;
        }
        return res;
    }

    //用于判断是否是二叉排序树时，测试使用，测试使用
    public boolean FindValue_A(int kx) {
        cur = root;
        boolean res = false;
        while (cur != null && cur.key != kx) {
            cur = kx < cur.key ? cur.leftchild : cur.rightchild;
        }

        //cur！=null说明 && cur.key == kx成立
        if (cur != null) {
            cur.key = 100;
            res = true;
        }
        return res;
    }


    //二叉排序树中，寻找ptr节点的直接后继节点
    private BstNode Next(BstNode ptr) {
        while (ptr != null && ptr.leftchild != null) {
            ptr = ptr.leftchild;
        }
        return ptr;
    }

    //删除值为kx 的节点
    //1、单分支（两种）  2、双分支   3、叶子结点
    public boolean Remove(int kx) {
        boolean res = false;
        if (root == null) return res;
        BstNode pa = null;
        cur = root;
        //查找kx过程
        while (cur != null && cur.key != kx) {
            pa = cur;
            cur = kx < cur.key ? cur.leftchild : cur.rightchild;
        }

        //没有找到该节点，删除失败，返回false
        if (cur == null) return res;

        //找到了该节点

        if (cur.leftchild != null && cur.rightchild != null) {
            BstNode nt = Next(cur.rightchild);
            cur.key = nt.key;       //删除转移
            //记录直接后继节点的父节点，用于连接直接后继节点的子节点
            pa = nt.parent;
            cur = nt;
        }//此时cur指向有要删除双子节点的节点的直接后继节点，删除已转移

        //指向右孩子的child
        BstNode child = cur.leftchild != null ? cur.leftchild : cur.rightchild;     //***good

        //单分支，右孩子不为空，把右孩子的双亲节点指向（原来的）父节点的父节点
        if (child != null) child.parent = pa;
        //leaf // one brch
        if (pa == null) {
            //cur是root节点，要删除的是root节点，并且是单分支
            root = child;
        } else {
            //单分支，确定右孩子作为，这里很精辟
            if (cur.key < pa.key) {
                pa.leftchild = child;
            } else {
                pa.rightchild = child;
            }
        }
        return true;
    }//终止都很精辟，要多练习侧能习惯


    private BstNode First(BstNode ptr) // Min 二叉排序树中最大的数
    {
        while (ptr != null && ptr.leftchild != null) {
            ptr = ptr.leftchild;
        }
        return ptr;
    }

    private BstNode Last(BstNode ptr)  // Max 二叉排序树中最小的数
    {
        while (ptr != null && ptr.rightchild != null) {
            ptr = ptr.rightchild;
        }
        return ptr;
    }

    //寻找后继节点
    private BstNode NextT(BstNode ptr) {
        if (ptr == null) return null;
        if (ptr.rightchild != null) {
            return First(ptr.rightchild);
        } else {
            BstNode pa = ptr.parent;
            while (pa != null && pa.leftchild != ptr) {
                ptr = pa;
                pa = ptr.parent;    //继续向高层父节点
            }//左孩子等于ptr时就是直接后继节点
            return pa;
        }
    }

    //寻找前驱节点
    private BstNode Prev(BstNode ptr) {
        if (ptr == null) return null;
        if (ptr.leftchild != null) {
            return Last(ptr.leftchild);
        } else {
            BstNode pa = ptr.parent;
            while (pa != null && pa.rightchild != ptr) {    //
                ptr = pa;
                pa = ptr.parent;
            }//右孩子等于ptr时就是直接前驱节点
            return pa;
        }

    }

    //升序打印二叉排序树，不用栈或者队列
    public void NiceInOrder_A() {
        for (BstNode p = First(root); p != null; p = NextT(p)) {
            System.out.print(p.key + " ");
        }
        System.out.println();
    }

    //降序打印二叉排序树，不用栈或者队列
    void ResNiceInOrder() {
        for (BstNode p = Last(root); p != null; p = Prev(p)) {
            System.out.print(p.key + " ");
        }
        System.out.println();
    }
}

public class TestDemo03 {
    public static void main(String[] args) {
        //二叉排序树的中序遍历就是，数列元素从小到大排序的结果
        int[] ar = {53, 17, 78, 9, 45, 65, 87, 23, 81, 94, 88, 92};
/**                     53
 *              17              78
 *          9       45       65      87
 *                23              81     94
 *                                     88
 *                                       92
 */
        BSTree myt = new BSTree();
        //插入的方式实现二叉树初始化
        for (int i = 0; i < ar.length; ++i) {
            myt.Insert(ar[i]);
        }
        //测试查找值53能否查找成功
        System.out.println("FindValue:" + myt.FindValue(53));
        System.out.println("SearchValue:" + myt.SearchValue(53));

        //判断是不是二分查找树
        myt.NiceInOrder();
        boolean res = myt.Is_BSTree();
        System.out.println("Is_BSTree:" + res);
//        myt.FindValue_A(87);
//        myt.NiceInOrder();
//        res = myt.Is_BSTree();
//        System.out.println(res);

        //测试删除节点
//        myt.Remove(53);
//        myt.NiceInOrder();

        System.out.println("测试把二叉排序树编程一个双向链表！");
        myt.NiceInOrder();
        myt.NicePreOrder();
//        myt.InOrderList();        //这里测试会改变二叉排序树的结构！！！！！！！！！
//        myt.PrintList();

        System.out.println("测试升序降序输出！");
//        myt.NiceInOrder();
        myt.NiceInOrder_A();
        System.out.println("测试降序降序输出！");
        myt.ResNiceInOrder();
    }
}